/*
 * Created by guoyh on Tue Dec 06 2022 15:40:40
 * leetcode NO.54 https://leetcode.cn/problems/spiral-matrix/
 */

#include <iostream>
// #include <vector>
#include <gtest/gtest.h>

using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> path;
        int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int>> visited(row, vector<int> (col, 0));
        int r = 0, c = 0;
        int directionIndex = 0;
        // 右、下、左、上的顺序
        vector<vector<int>> directions = {{0,1},{1, 0},{0, -1},{-1, 0}};

        for(int i = 0; i < row * col; i++){
            path.push_back(matrix[r][c]);
            visited[r][c] = 1;
            int nextRow = r + directions[directionIndex][0], nextCol = c + directions[directionIndex][1];
            // 行、列 参数出界，或者碰到访问过的数字，那么改变方向: 右、下、左、上
            // 判断下一个位置(nextRow, nextCol) 是否访问过，不是当前位置，当前位置一定是访问过的（r,c）
            if(nextRow >= row || nextCol >= col || nextRow < 0 || nextCol < 0 || visited[nextRow][nextCol]){
                directionIndex = (directionIndex + 1) % 4;
            }
            // 更新访问位置（坐标）
            r += directions[directionIndex][0];
            c += directions[directionIndex][1];
        }

        return path;

    }
};

class TestFixture : public ::testing::Test{
protected:
    vector<vector<int>> res = {{{1,2,3},{4,5,6},{7,8,9}}};
    vector<vector<int>> res1 = {{1,2,3,4}, {5,6,7,8},{9,10,11,12}};

    Solution slu;
    void SetUp() override{
    }

};

TEST_F(TestFixture, AddTest) {
    vector<int> ret = slu.spiralOrder(res);
    EXPECT_EQ(ret.size(), 9);
}

int main(int argc, char *argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

